Message Authentication (Message Authentication Code (MAC)) is a technology in which a particular party that knows secret key K appends a tag T, that can be computed by using secret key K, to message M that is to be transmitted to ensure the validity of the message.
For example, when a sender has transmitted message M and tag T to a receiver in communication between two parties that share secret key K, the tag is computed from the message that was received on the receiver side and the tag that was computed is then compared with the tag that was received. If, as a result of comparison, the tag that was computed matches the tag that was received, message M can be judged to be a message sent from a legitimate sender. On the other hand, if the tag that was computed does not match the tag that was received, the message can be judged as not a message that was sent from a legitimate sender or can be detected as having been altered by a third party during communication.
Methods of message authentication include methods in which a first communication apparatus that transmits message M holds state variables such as counters (stateful MAC) and methods in which state variables are not held (stateless MAC). The stateless MAC methods further include methods (randomized MAC) that permit the generation of a uniform random number U that is independent of message M each time by the first communication apparatus that transmits message M and also includes methods (deterministic MAC) other than the randomized MAC methods.
In MAC that use state variables or random numbers, these values are used both in the generation of tag T and in the transmission of tag T by way of the communication channel to the destination of message M without being encrypted. Tag T that is generated in randomized MAC can be represented as T=F(K, M, U), where F represents an encryption function, K represents a key of encryption function F, M represents a message, and U represents a random number. The first communication apparatus transmits random number U, message M, and tag T to a second communication apparatus. The second communication apparatus, which is the destination of message M, having received random number U′, message M′, and tag T′ that have been transmitted in by way of the communication channel, finds tag T1 for verification from message M′ and random number U′ that were received and secret key K that is identical to secret key K that is stored by the first communication apparatus and, by comparing tag T1 for verification with tag T′ that was transmitted in, determines whether random number U′, message M′, and tag T′ that have been received have been altered while being transmitted in by way of the communication channel.
In the following explanation, a case is described as an example in which the number of bits of random number U is n bits and the number of bits of tag T is s bits (where s is a positive integer equal to or less than n). In addition, message M is a binary sequence (bit string) of any number of bits, but in the interest of simplifying the explanation, a case is described as an example in which the maximum value of the number of bits of message M is L.
In randomized MAC, keyed encryption function F that receives data of any number of bits that is the same as the number of bits n of random number U and supplies the data that have been encrypted that are of a number of bits identical to the number of bits n of random number U (hereinbelow referred to as “n-bit input/output”) and keyed hash function H that receives data of variable length as input and that supplies a hash value of a number of bits that is identical to the number of bits n of random number U are used to compute tag T as the following Formula 1:[Formula 1]T=chop(F(Ke,U)+H(Kh,M))  (Formula 1)
Here, Ke shown in Formula 1 is the key of encryption function F and Kh is the key of hash function H. In addition, the symbol “+” is an arithmetic symbol that indicates the exclusive OR for each bit. In addition, chop(x) is a function for extracting the value contained in bits of a predetermined number of bits s from among x.
Keyed encryption function F is a sufficiently safe function referred to as a pseudorandom function. A block code such as AES (Advanced Encryption Standard) is typically used as keyed encryption function F.
In Hash function H, it is desired that when two different messages M and M′ are applied as input, the probability Pr that each of the hash values that are supplied to respective messages M and M′ will match is extremely small. In other words, in Hash function H, it is desired that the following Formula 2 holds true for the pair (M, M′) of messages M and M′ that differ from each other in which the bit number is equal to or less than an arbitrary number of bits L for any positive number e that is sufficiently small.[Formula 2]Pr[H(Kh,M)=H(Kh,M)]≦e  (Formula 2)
Because an arbitrary positive number e cannot be smaller than the reciprocal of the output size of hash function H, in this case, the minimum value of positive number e is 2(n). In addition, because positive number e can take the maximum value L of the number of bits of message M that is the object of computation of hash value S as a parameter, the notation e(L) is appropriate. However, in the following explanation, a case is taken by way of example in which the maximum value L of the number of bits of message M is treated as a constant and e(L) is abbreviated as “e.” This type of function is referred to as an “e-almost universal hash function” and effective construction is possible by means of an algebraic constitutive method such as a polynomial operation on a finite field. A randomized MAC that is constructed in this way is referred to as a randomized Carter-Wegman MAC (randomized CW-MAC).
A typical definition of the safety of a randomized MAC is next described. An attack scenario in a randomized MAC can be divided into two phases, a tag generation phase and a forgery phase. First, in the tag generation phase, a third party that carries out an attack uses a third communication apparatus that differs from the first communication apparatus and a second communication apparatus to acquire Qmac items of data that contain random number U, message M and tag T that are transmitted in from the first communication apparatus for any message M that can be selected. Next, in the forgery phase, the third party uses the third communication apparatus to generate Qver items of forged data that contain random number U′, message M′, and tag T′ based on the Qmac items of data (random number U, message M and tag T) that were acquired in the tag generation phase and transmits the forged data to the second communication apparatus. The attack is considered to have been successful if the second communication apparatus then judges that at least one item of forged data of the forged data (random number U′, message M′, and tag T′) that was transmitted in from the communication apparatus of the third party is data that have been transmitted from the first communication apparatus and that have not been altered.
The forged data here described may be any type of data as long as they are data that differ from data (random number U, message M, and tag T) that were transmitted by the first communication apparatus that was observed by the third party in the tag generation phase. For example, (random number U′, message M, tag T) which is data that only random number U has been altered to a different random number U′ in data (random number U, message M, and tag T) that were observed in the tag generation phase, may be generated as forged data. This concept of safety is referred to as “strong unforgeability.” As a standard of safety, a case in which a message that is contained in forged data is required to differ from message M that was observed in the tag generation phase is referred to as “weak unforgeability.”
The relation expressed by the following Formula 3 holds for the probability of success in forgery in the sense of the strong unforgeability of randomized CW-MAC that employs the hash function H and keyed encryption function F.[Formula 3]Suc(Qmac,Qver,time)≦Sec(F,Qmac+Qver,time1)+Qmac2/2″+Qver(e+½s)  (Formula 3)
Here, Suc(Qmac, Qver, time) shown on the left side of Formula 3 represents the probability of success of forgery in a case in which a third party acquires Qmac items of transmitted data in the tag generation phase, generates Qver items of forged data in the forgery phase, and the overall amount of computation is “time.” In addition, Sec(F, Qmac+Qver, time′) shown on the right side of Formula 3 represents the maximum gain (discrimination success probability−(½)) when the third party has carried out discrimination of keyed encryption function F by means of a chosen plaintext attack in which the amount of computation is “time” and a true random function for generating a random number U “Qmac+Qver” times in a black box state. The computation amount “time” is a polynomial order of computation amount “time.”
From the above-described Formula 3, it can be seen that there are three conditions necessary for adequately reducing the probability of forgery in randomized CW-MAC: that keyed function F be a pseudorandom function that has sufficient safety against “Qmac+Qver” instances of chosen plaintext attack; that the number Qmac of items of data that a third party acquires be extremely small compared to 2(n/2) and that the number Qver of items of forged data generated by the third party be extremely small compared to each of positive number e and ½s.
The condition that is particularly problematic in terms of improving safety against attacks is the second condition of these three conditions. The reason for this is that the number Qmac of items of data (random number U, message M, and tag T) that are acquired by a third party can be made extremely large by the static observation of a communication channel by the third party. On the other hand, the number Qver of items of forged data generated by a third party is typically a value that is far smaller than Qmac because interference on the communication channel can be perceived when failures of message authentication occur with frequency in the second communication apparatus that is receiving forged data. In addition, the exponent of the Qmac term is “2,” while the exponent of the term of Qver that is the number of items of forged data is “1.” As a result, when the number of bits n of random number U and the number of bits s of tag T are identical to the reciprocal of positive number e (i.e., when n=1/e=s), when the term Qver increases, it increases extremely slowly compared to Qmac. Based on the above considerations, it is believed that Qmac actually coincides with the life of the MAC key. In other words, after transmitting message M a number of times that is far smaller than 2(n/2) in the above-described randomized CW-MAC, key K for tag T generation must be updated regardless of the presence or absence of attacks. This property means that the Key LifeTime, (hereinbelow abbreviated as “KLT”), which is the maximum value of the number of times a message can be transmitted by a particular key K, is “n/2.” In addition, the maximum value of Qmac that is 2(n/2) is referred to as the “birthday bound” for n.
As a method for making this KLT greater than n/2, a MACRX method such as disclosed in Non-Patent Document 1 can be considered. This MACRX method involves making the number of bits of random number U greater than the number of bits n. For example, when the number of bits of random number U is “3×n” bits and the number of bits of tag T is n bits, tag T that is generated in the MACRX method is represented by the following Formula 4:[Formula 4]T=F(Ke,U1)+F(Ke,U2)+F(Ke,U3)+H(Kh,M)  (Formula 4)
Each of random numbers U1, U2, and U3 shown in Formula 4 are independent uniform random numbers for which the number of bits is n bits. Thus, in the MACRX method, a first communication apparatus transmits random numbers U1, U2, and U3, message M, and tag T to a second communication apparatus. However, because a mere reordering of random numbers U1, U2, and U3 can achieve a successful forgery, only unforgeability in the weak sense can be guaranteed. In order to ensure strong unforgeability in the MACRX, random numbers U1, U2, U3 must be transmitted after subjecting these random numbers to appropriate encoding.
According to Non-Patent Document 1, the weak unforgeability of the MACRX method can be represented by the following Formula 5:[Formula 5]Suc(Qmac,Qver,time)≦Sec(F,3(Qmac+Qver),time′)+d(3,n)Qmac3/23n+Qver e  (Formula 5)
Because d(3, n) shown in Formula 5 is actually a small value, it can be seen that KLT is substantially n. In the MACRX method, it is further indicated that KLT remains unchanged as “n/2” when the number of bits of random number U is made less than or equal to 2n bits.
Non-Patent Document 2 discloses a format that includes random number U among the data that are applied as input to hash function H in randomized MAC, i.e., a method of generating tag T such as represented in Formula 6 below:[Formula 6]T=F(Ke,H(Kh,U∥M))  (Formula 6)
The symbol “∥” shown in FIG. 6 indicates the coupling of random number U and message M. However, in the technique disclosed in Non-Patent Document 2, hash function H is also applied to random number U in order to limit the increase of the probability e that the hash values obtained in each case will conflict with each other as the maximum value L of the number of bits of each message increases when hash function H is applied to each of messages that differ from each other. As a result, KLT in this technique remains unchanged as “n/2” and cannot be made greater than “n/2.”
Non-Patent Document 3 and Patent Document 1 disclose that the KLT of a Carter-Wegman MAC is substantially n when state variables such as counters are used in place of random numbers, and moreover, when a sufficiently good universal hash function and n-bit input/output encryption function F are used to generate tag T. In these cases, however, the communication apparatus that transmits message M must hold the state variables such as counters. As a result, the use of a plurality of devices that use the same key in these techniques entails the disadvantage that establishing synchronization among the devices is necessary.
In addition, Non-Patent Document 4 discloses a method that can make KLT substantially n in a deterministic MAC that does not employ random numbers or counters. However, the number of bits of data that are applied as input to encryption function F in this technique is 2n bits or more, and this technique is therefore problematic because it cannot be applied to MACRX or randomized Carter-Wegman MAC that have different preconditions.
The above-described Patent Document 1 and Non-Patent Documents 1-4 are as shown below: